package com.ian.day;

import java.util.Arrays;

/**
 *
 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

 换句话说，第一个字符串的排列之一是第二个字符串的子串。

 示例1:

 输入: s1 = "ab" s2 = "eidbaooo"
 输出: True
 解释: s2 包含 s1 的排列之一 ("ba").


 示例2:

 输入: s1= "ab" s2 = "eidboaoo"
 输出: False


 注意：

 输入的字符串只包含小写字母
 两个字符串的长度都在 [1, 10,000] 之间

 */
public class CheckInclusion {

    public boolean checkInclusion(String s1, String s2) {
        if(s1.length() > s2.length())
            return false;
        //left,right表示整个窗口的范围
        int sum = 0,count = 0,left = 0,right = s1.length()-1;
        char[] chars = s1.toCharArray();
        char[] chars1 = s2.toCharArray();
        //统计s1的字符个数
        int counts[] = new int[26];
        for(int i = left;i <= right;i++){
            sum += chars[i];
            counts[chars[i] - 'a']++;
            count += chars1[i];
        }
        if(sum == count) {
            int counts1[] = new int[26];
            for (int i = left; i <= right; i++)
                counts1[chars1[i] - 'a']++;
            //比较两个数组是否相等，如果相等则返回true
            if (Arrays.equals(counts,counts1))
                return true;
        }
        //滑动窗口并重复上述的操作
        while(right < s2.length() - 1){
            if(right+1 < s2.length()){
                count = count - s2.charAt(left++) + s2.charAt(++right);
                if(sum == count) {
                    int counts1[] = new int[26];
                    for (int i = left; i <= right; i++)
                        counts1[chars1[i] - 'a']++;
                    if (Arrays.equals(counts,counts1))
                        return true;
                }
            }
        }
        return false;
    }
}
